package com.interview.sample;

public class Bitmap {
    private int[] bitmap;
    private int size;

    /**
     * 构造函数，初始化位图的大小
     * @param maxPhoneNumber 电话号码的最大值，用于确定位图的大小
     */
    public Bitmap(int maxPhoneNumber) {
        if (maxPhoneNumber < 0) {
            throw new IllegalArgumentException("电话号码不能为负数");
        }
        // 计算需要多少个 int 来存储位图
        size = (maxPhoneNumber / 32) + 1;
        bitmap = new int[size];
    }

    /**
     * 插入一个电话号码到位图中
     * @param phoneNumber 要插入的电话号码
     */
    public void insert(int phoneNumber) {
        if (phoneNumber < 0) {
            throw new IllegalArgumentException("电话号码不能为负数");
        }
        // 计算电话号码对应的数组下标和位偏移量
        int index = phoneNumber / 32;
        int offset = phoneNumber % 32;

        // 确保电话号码不超过位图的大小
        if (index >= size) {
            throw new IndexOutOfBoundsException("电话号码超出位图范围");
        }

        // 设置对应位为 1
        bitmap[index] |= (1 << offset);
    }

    /**
     * 检查一个电话号码是否存在于位图中
     * @param phoneNumber 要检查的电话号码
     * @return 存在返回 true，否则返回 false
     */
    public boolean checkExist(int phoneNumber) {
        if (phoneNumber < 0) {
            throw new IllegalArgumentException("电话号码不能为负数");
        }
        // 计算电话号码对应的数组下标和位偏移量
        int index = phoneNumber / 32;
        int offset = phoneNumber % 32;

        // 检查是否超过位图的范围
        if (index >= size) {
            return false; // 超出范围，不存在
        }

        // 检查对应位是否为 1
        return (bitmap[index] & (1 << offset)) != 0;
    }

    public static void main(String[] args) {
        // 示例：最大电话号码为 100
        Bitmap bitmap = new Bitmap(100);

        // 插入电话号码
        bitmap.insert(1);
        bitmap.insert(5);
        bitmap.insert(31);
        bitmap.insert(32);
        bitmap.insert(63);
        bitmap.insert(64);

        // 查询电话号码是否存在
        System.out.println(bitmap.checkExist(1));   // true
        System.out.println(bitmap.checkExist(31));  // true
        System.out.println(bitmap.checkExist(32));  // true
        System.out.println(bitmap.checkExist(63));  // true
        System.out.println(bitmap.checkExist(64));  // true
        System.out.println(bitmap.checkExist(100)); // false（超出范围）
    }
}